
上一节中，用TableGen语言定义了记录。使用这些记录，需要编写自己的TableGen后端，该后端可以生成C++源代码或使用记录作为输入执行其他操作。

第3章中，Lexer类的实现使用数据库文件来定义标记和关键字，各种查询函数使用该数据库文件。除此之外，数据库文件还用于实现关键字过滤器。关键字过滤器是一个哈希映射，使用llvm::StringMap类实现。当找到一个标识符时，就调用关键字过滤器来确定该标识符是否实际上是一个关键字。若仔细看看ppprofiler通道的实现，则将看到该函数经常调用，所以实现该功能很有用。

然而，这并不像看起来那么容易。例如，可以尝试用二进制搜索替换散列映射中的查找。这需要对数据库文件中的关键字进行排序。目前，在开发过程中，一个新的关键字可能会添加到错误的地方。确保关键字按正确顺序排列的唯一方法是，添加一些在运行时检查顺序的代码。

可以通过更改内存布局来加快标准二进制搜索。可以使用Eytzinger布局，而不是对关键字进行排序，其以宽度优先的顺序枚举搜索树。这种布局增加了数据的缓存局部性，加快了搜索速度。就我个人而言，不可能用手动的方式，在数据库文件中以宽度优先的顺序维护关键字。

另一种流行的搜索方法是生成最小完美哈希函数。若将新键插入动态哈希表(如llvm::StringMap)，则该键可能会映射到已占用的槽，这称为键碰撞。键冲突是不可避免的，已经开发了许多策略来缓解这个问题。但若知道所有的键，就可以构建没有键冲突的哈希函数，这样的哈希函数堪称完美。若不需要比键更多的槽，则称为最小键。可以高效地生成完美的哈希函数——例如，使用gperf GNU工具。

总而言之，使用关键字生成查找函数一定有原因，让我们将数据库文件转成到TableGen!

\mySubsubsection{8.4.1.}{用TableGen语言定义数据}

TokenKinds.def数据库文件定义了三个不同的宏。TOK宏用于没有固定拼写的令牌——用于整数字面值。PUNCTUATOR宏用于所有类型的标点符号，并包含首选拼写。KEYWORD宏定义了一个由字面量和一个标志组成的关键字，这个标志用于指示这个字面量在哪个语言级别上是关键字。例如，C++11中就添加了thread\_local关键字。

TableGen语言中用来表达关键字的方法是，创建一个保存所有数据的Token类。然后，可以添加该类的子类，还需要一个Flag类，用于与关键字一起定义的标志，还需要一个类来定义关键字过滤器。这些类定义了基本的数据结构，可以在其他项目中重用，可以创建了一个Keyword.td文件:

\begin{enumerate}
\item
标志为名称和相关联的值建模，使用这些数据生成一个枚举很容易:

\begin{shell}
class Flag<string name, int val> {
    string Name = name;
    int Val = val;
}
\end{shell}

\item
Token类用作基类，只是有一个名字。注意，这个类没有参数:

\begin{shell}
class Token {
    string Name;
}
\end{shell}

\item
Tok类与数据库文件中相应的Tok宏具有相同的功能，表示没有固定拼写的标记。它派生自基类Token，只是为名称添加了初始化:

\begin{shell}
class Tok<string name> : Token {
    let Name = name;
}
\end{shell}

\item
以同样的方式，标点器类类似于PUNCTUATOR宏，为标记的拼写添加了一个字段:

\begin{shell}
class Punctuator<string name, string spelling> : Token {
    let Name = name;
    string Spelling = spelling;
}
\end{shell}

\item
最后，Keyword类需要一个标志列表:

\begin{shell}
class Keyword<string name, list<Flag> flags> : Token {
    let Name = name;
    list<Flag> Flags = flags;
}
\end{shell}

\item
有了这些定义，现在可以为关键字过滤器定义一个类，称为TokenFilter。其接受标记列表作为参数:

\begin{shell}
class TokenFilter<list<Token> tokens> {
    string FunctionName;
    list<Token> Tokens = tokens;
}
\end{shell}
\end{enumerate}

使用这些类定义，就能够从TokenKinds.def数据库文件中捕获所有数据。TinyLang语言不使用标志，但实际使用的语言，如C和C++经历了几次修订，通常需要标记。因此，我们使用C和C++中的关键字作为示例，来创建一个KeywordC.td文件:

\begin{enumerate}
\item
首先，包含前面创建的类定义:

\begin{shell}
Include "Keyword.td"
\end{shell}

\item
接下来，定义标志，该值为该标志的二进制值。注意，如何使用!or操作符来为KEYALL标志创建值:

\begin{shell}
def KEYC99 : Flag<"KEYC99", 0x1>;
def KEYCXX : Flag<"KEYCXX", 0x2>;
def KEYCXX11: Flag<"KEYCXX11", 0x4>;
def KEYGNU : Flag<"KEYGNU", 0x8>;
def KEYALL : Flag<"KEYALL",
                    !or(KEYC99.Val, KEYCXX.Val,
                        KEYCXX11.Val , KEYGNU.Val)>;
\end{shell}

\item
有些符号没有固定的拼写，例如注释:

\begin{shell}
def : Tok<"comment">;
\end{shell}

\item
操作符是使用Punctuator类定义:

\begin{shell}
def : Punctuator<"plus", "+">;
def : Punctuator<"minus", "-">;
\end{shell}

\item
关键字需要使用不同的标志:

\begin{shell}
def kw_auto: Keyword<"auto", [KEYALL]>;
def kw_inline: Keyword<"inline", [KEYC99,KEYCXX,KEYGNU]>;
def kw_restrict: Keyword<"restrict", [KEYC99]>;
\end{shell}

\item
最后，是关键字过滤器的定义:

\begin{shell}
def : TokenFilter<[kw_auto, kw_inline, kw_restrict]>;
\end{shell}
\end{enumerate}

当然，该文件不包括C和C++中的所有标记，其演示了定义的TableGen类的所有可能用法。

基于这些TableGen文件，我们将在下一节中实现TableGen后端。

\mySubsubsection{8.4.2.}{实现TableGen后端}

由于解析和创建记录是通过LLVM库完成的，只需要关心后端实现，主要由基于记录中的信息生成C++源代码片段组成。需要清楚要生成什么源代码，才能将其放入后端。

\mySamllsection{绘制要生成的源码的草图}

TableGen工具的输出是一个包含C++片段的文件，这些片段由宏保护。目标是替换TokenKinds.def数据库文件。根据TableGen文件中的信息，可以生成以下内容:

\begin{enumerate}
\item
用于定义标志的枚举成员。开发者可以自由命名类型，但应该基于无符号类型。若生成的文件名为TokenKinds.inc，预期的使用方式为:

\begin{cpp}
enum Flags : unsigned {
    #define GET_TOKEN_FLAGS
    #include "TokenKinds.inc"
}
\end{cpp}

\item
TokenKind枚举，以及getTokenName()、getPunctuatorSpelling()和getKeywordSpelling()函数的原型和定义。这段代码替换了TokenKinds.def数据库文件，大部分TokenKinds.h包含文件和TokenKinds.cpp源文件。

\item
新的lookupKeyword()函数，可以用来代替使用llvm::StringMap类型的当前实现，这就是要优化的函数。
\end{enumerate}

了解了想要生成的内容，就可以开始实现后端了。

\mySamllsection{创建一个新的TableGen工具}

新工具使用一个驱动程序，该驱动计算命令行选项，并在不同的文件中调用生成函数和实际的生成器函数。我们将驱动文件命名为TableGen.cpp，将包含生成器的文件命名为TokenEmitter.cpp，还需要TableGenBackends.h头文件。让我们从生成TokenEmitter.cpp文件中的C++代码开始实现:

\begin{enumerate}
\item
像往常一样，文件以包含所需的头文件开始。最重要的是llvm/TableGen/Record.h，定义了Record类，用于保存解析.td文件生成的记录:

\begin{cpp}
#include "TableGenBackends.h"
#include "llvm/Support/Format.h"
#include "llvm/TableGen/Record.h"
#include "llvm/TableGen/TableGenBackend.h"
#include <algorithm>
\end{cpp}

\item
为了简化编码，导入了llvm命名空间:

\begin{cpp}
using namespace llvm;
\end{cpp}

\item
TokenAndKeywordFilterEmitter类负责生成C++源代码。如前一节所述，emitFlagsFragment()、emitTokenKind()和emitKeywordFilter()方法会生成源代码，其中包含要生成的源代码的草图。唯一的公共方法run()调用了所有编写代码的方法，记录保存在RecordKeeper的一个实例中，并作为参数传递给构造函数。这个类位于匿名命名空间中:

\begin{cpp}
namespace {
class TokenAndKeywordFilterEmitter {
    RecordKeeper &Records;

public:
    explicit TokenAndKeywordFilterEmitter(RecordKeeper &R)
        : Records(R) {}

    void run(raw_ostream &OS);

private:
    void emitFlagsFragment(raw_ostream &OS);
    void emitTokenKind(raw_ostream &OS);
    void emitKeywordFilter(raw_ostream &OS);
};
} // End anonymous namespace
\end{cpp}

\item
run()方法调用所有发出方法，也乘以每个相位的长度。可用-{}-time-phases选项设置，再在所有代码生成后显示时间:

\begin{cpp}
void TokenAndKeywordFilterEmitter::run(raw_ostream &OS) {
    // Emit Flag fragments.
    Records.startTimer("Emit flags");
    emitFlagsFragment(OS);

    // Emit token kind enum and functions.
    Records.startTimer("Emit token kind");
    emitTokenKind(OS);

    // Emit keyword filter code.
    Records.startTimer("Emit keyword filter");
    emitKeywordFilter(OS);
    Records.stopTimer();
}
\end{cpp}

\item
emitFlagsFragment()方法显示了生成C++源代码的函数的典型结构，生成的代码由GET\_TOKEN\_FLAGS宏保护。要生成C++源片段，需要循环遍历TableGen文件中从Flag类派生的所有记录。有了这样的记录，就很容易查询记录的名称和值。注意，名称Flag、Name和Val必须与TableGen文件中的完全相同。若在TableGen文件中将Val重命名为Value，则还需要更改此函数中的字符串。所有生成的源代码都写入提供的流，OS:

\begin{cpp}
void TokenAndKeywordFilterEmitter::emitFlagsFragment(
raw_ostream &OS) {
    OS << "#ifdef GET_TOKEN_FLAGS\n";
    OS << "#undef GET_TOKEN_FLAGS\n";
    for (Record *CC :
            Records.getAllDerivedDefinitions("Flag")) {
        StringRef Name = CC->getValueAsString("Name");
        int64_t Val = CC->getValueAsInt("Val");
        OS << Name << " = " << format_hex(Val, 2) << ",\n";
    }
    OS << "#endif\n";
}
\end{cpp}

\item
emitTokenKind()方法发出标记分类函数的声明和定义。先看一下如何发出声明，整体结构与前一种方法相同——只是要生成更多的C++源码，生成的源码由GET\_TOKEN\_KIND\_DECLARATION宏保护。注意，此方法尝试生成格式良好的C++代码，使用新行和缩进，就像人类开发者一样。若生成的源码不正确，并且需要检查它以找到错误，这将非常有帮助。也很容易犯这样的错误:毕竟，正在编写一个生成C++源代码的C++函数。

首先，生成TokenKind枚举。关键字的名称应该以kw\_字符串作为前缀。循环遍历Token类的所有记录，若也是Keyword类的子类，则可以查询这些记录，生成的前缀为:

\begin{cpp}
    OS << "#ifdef GET_TOKEN_KIND_DECLARATION\n"
        << "#undef GET_TOKEN_KIND_DECLARATION\n"
        << "namespace tok {\n"
        << " enum TokenKind : unsigned short {\n";
    for (Record *CC :
            Records.getAllDerivedDefinitions("Token")) {
        StringRef Name = CC->getValueAsString("Name");
        OS << " ";
        if (CC->isSubClassOf("Keyword"))
        OS << "kw_";
        OS << Name << ",\n";
    }
    OS << " NUM_TOKENS\n"
       << " };\n";
\end{cpp}

\item
接下来，生成函数声明。这只是一个常量字符串，这将完成声明生成:

\begin{cpp}
    OS << " const char *getTokenName(TokenKind Kind) "
            "LLVM_READNONE;\n"
        << " const char *getPunctuatorSpelling(TokenKind "
            "Kind) LLVM_READNONE;\n"
        << " const char *getKeywordSpelling(TokenKind "
            "Kind) "
            "LLVM_READNONE;\n"
        << "}\n"
        << "#endif\n";
\end{cpp}

\item
现在，转向生成定义。同样，生成的代码由一个名为GET\_TOKEN\_KIND\_DEFINITION的宏保护。首先，将标记名称发送到TokNames数组中，getTokenName()函数使用该数组检索名称。注意，当在字符串中使用引号符号时，必须转义为\verb|\|":

\begin{cpp}
    OS << "#ifdef GET_TOKEN_KIND_DEFINITION\n";
    OS << "#undef GET_TOKEN_KIND_DEFINITION\n";
    OS << "static const char * const TokNames[] = {\n";
    for (Record *CC :
        Records.getAllDerivedDefinitions("Token")) {
        OS << " \"" << CC->getValueAsString("Name")
           << "\",\n";
    }
    OS << "};\n\n";
    OS << "const char *tok::getTokenName(TokenKind Kind) "
          "{\n"
       << " if (Kind <= tok::NUM_TOKENS)\n"
       << " return TokNames[Kind];\n"
       << " llvm_unreachable(\"unknown TokenKind\");\n"
       << " return nullptr;\n"
       << "};\n\n";
\end{cpp}

\item
接下来，生成getPunctuatorSpelling()函数。与其他部分的区别是，循环遍历从punctuation类派生的所有记录。还会生成一个switch语句，而不是一个数组:

\begin{cpp}
    OS << "const char "
          "*tok::getPunctuatorSpelling(TokenKind "
          "Kind) {\n"
       << " switch (Kind) {\n";
    for (Record *CC :
            Records.getAllDerivedDefinitions("Punctuator")) {
        OS << " " << CC->getValueAsString("Name")
           << ": return \""
           << CC->getValueAsString("Spelling") << "\";\n";
    }
    OS << " default: break;\n"
       << " }\n"
       << " return nullptr;\n"
       << "};\n\n";
\end{cpp}

\item
最后，生成getKeywordSpelling()函数。代码类似于发出getPunctuatorSpelling()，这次循环遍历Keyword类的所有记录，并且该名称以kw\_为前缀:

\begin{cpp}
    OS << "const char *tok::getKeywordSpelling(TokenKind "
          "Kind) {\n"
       << " switch (Kind) {\n";
    for (Record *CC :
         Records.getAllDerivedDefinitions("Keyword")) {
        OS << " kw_" << CC->getValueAsString("Name")
           << ": return \"" << CC->getValueAsString("Name")
           << "\";\n";
    }
    OS << " default: break;\n"
       << " }\n"
       << " return nullptr;\n"
       << «};\n\n»;
    OS << «#endif\n»;
}
\end{cpp}

\item
因为生成过滤器需要从记录中收集一些数据，所以emitKeywordFilter()方法比前面的方法更复杂。生成的源代码使用std::lower\_bound()函数，从而实现二分查找。

TableGen文件中可以定义TokenFilter类的多个记录。出于演示目的，最多只生成一个标记过滤器方法:

\begin{cpp}
    std::vector<Record *> AllTokenFilter =
        Records.getAllDerivedDefinitionsIfDefined(
            "TokenFilter");
    if (AllTokenFilter.empty())
        return;
\end{cpp}

\item
用于筛选器的关键字位于名为Tokens的列表中。要访问该列表，首先需要查找记录中的Tokens字段。这将返回一个指向RecordVal类实例的指针，可以通过调用方法getValue()从中检索Initializer实例。Tokens字段可定义为一个列表，可将初始化器实例强制转换为ListInit。若失败，则退出该函数:

\begin{cpp}
    ListInit *TokenFilter = dyn_cast_or_null<ListInit>(
        AllTokenFilter[0]
            ->getValue("Tokens")
            ->getValue());
    if (!TokenFilter)
        return;
\end{cpp}

\item
现在，可以构造一个过滤器表了。对于TokenFilter列表中存储的每个关键字，需要Flag字段的名称和值。该字段再次定义为列表，因此需要遍历这些元素以计算最终值。结果名称/标志值对存储在Table vector中:

\begin{cpp}
    using KeyFlag = std::pair<StringRef, uint64_t>;
    std::vector<KeyFlag> Table;
    for (size_t I = 0, E = TokenFilter->size(); I < E;
            ++I) {
        Record *CC = TokenFilter->getElementAsRecord(I);
        StringRef Name = CC->getValueAsString("Name");
        uint64_t Val = 0;
        ListInit *Flags = nullptr;
        if (RecordVal *F = CC->getValue("Flags"))
            Flags = dyn_cast_or_null<ListInit>(F->getValue());
        if (Flags) {
            for (size_t I = 0, E = Flags->size(); I < E; ++I) {
                Val |=
                Flags->getElementAsRecord(I)->getValueAsInt(
                "Val");
            }
        }
        Table.emplace_back(Name, Val);
    }
\end{cpp}

\item
为了能够执行二分查找，需要对表进行排序。比较函数由Lambda函数提供:

\begin{cpp}
    llvm::sort(Table.begin(), Table.end(),
                [](const KeyFlag A, const KeyFlag B) {
                    return A.first < B.first;
                });
\end{cpp}

\item
现在，可以生成C++源代码了。首先，生成包含关键字名称和相关标志值的排序表:

\begin{cpp}
    OS << "#ifdef GET_KEYWORD_FILTER\n"
       << "#undef GET_KEYWORD_FILTER\n";
    OS << "bool lookupKeyword(llvm::StringRef Keyword, "
          "unsigned &Value) {\n";
    OS << " struct Entry {\n"
       << " unsigned Value;\n"
       << " llvm::StringRef Keyword;\n"
       << " };\n"
       << "static const Entry Table[" << Table.size()
       << "] = {\n";
    for (const auto &[Keyword, Value] : Table) {
        OS << " { " << Value << ", llvm::StringRef(\""
           << Keyword << "\", " << Keyword.size()
           << ") },\n";
    }
    OS << " };\n\n";
\end{cpp}

\item
接下来，使用标准C++函数std::lower\_bound()在排序表中查找关键字。若关键字在表中，则Value参数接收与关键字关联的标志的值，函数返回true。否则，函数返回false:

\begin{cpp}
    OS << " const Entry *E = "
            "std::lower_bound(&Table[0], "
            "&Table["
       << Table.size()
       << "], Keyword, [](const Entry &A, const "
            "StringRef "
            "&B) {\n";
    OS << " return A.Keyword < B;\n";
    OS << " });\n";
    OS << " if (E != &Table[" << Table.size()
       << "]) {\n";
    OS << " Value = E->Value;\n";
    OS << " return true;\n";
    OS << " }\n";
    OS << " return false;\n";
    OS << "}\n";
    OS << "#endif\n";
}
\end{cpp}

\item
现在唯一缺少的部分是调用该实现的方法，为此定义了一个全局函数EmitTokensAndKeywordFilter()。在llvm/TableGen/TableGenBackend.h头文件中声明的emitSourceFileHeader()函数，在生成的文件的顶部生成注释:

\begin{cpp}
void EmitTokensAndKeywordFilter(RecordKeeper &RK,
                                raw_ostream &OS) {
    emitSourceFileHeader("Token Kind and Keyword Filter "
                        "Implementation Fragment",
                        OS);
    TokenAndKeywordFilterEmitter(RK).run(OS);
}
\end{cpp}
\end{enumerate}

这样，就在TokenEmitter.cpp文件中完成了源生成器的实现，代码不算太复杂。

TableGenBackends.h头文件只包含EmitTokensAndKeywordFilter()函数的声明。为了避免包含其他文件，可以对raw\_ostream和RecordKeeper类使用前向声明:

\begin{cpp}
#ifndef TABLEGENBACKENDS_H
#define TABLEGENBACKENDS_H

namespace llvm {
    class raw_ostream;
    class RecordKeeper;
} // namespace llvm

void EmitTokensAndKeywordFilter(llvm::RecordKeeper &RK,
                                llvm::raw_ostream &OS);
#endif
\end{cpp}

缺少的部分是驱动程序的实现，其任务是解析TableGen文件并根据命令行选项发出记录。实现在TableGen.cpp文件中:

\begin{itemize}
\item
与往常一样，实现从包含所需的头文件开始。最重要的一个是llvm/TableGen/Main.h，这个头文件声明了TableGen的前端:

\begin{cpp}
#include "TableGenBackends.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/PrettyStackTrace.h"
#include "llvm/Support/Signals.h"
#include "llvm/TableGen/Main.h"
#include "llvm/TableGen/Record.h"
\end{cpp}

\item
为了简化编码，导入了llvm命名空间:

\begin{cpp}
using namespace llvm;
\end{cpp}

\item
用户可以选择一个操作，ActionType枚举包含所有可能的操作:

\begin{cpp}
enum ActionType {
    PrintRecords,
    DumpJSON,
    GenTokens,
};
\end{cpp}

\item
使用一个名为Action的命令行选项对象。用户需要指定-{}-gen-tokens选项，以生成实现的令牌过滤器。另外两个选项-{}-print-records和-{}-dump-json是转储读记录的标准选项。注意，该对象位于匿名命名空间中:

\begin{cpp}
namespace {
cl::opt<ActionType> Action(
    cl::desc("Action to perform:"),
    cl::values(
        clEnumValN(
            PrintRecords, "print-records",
            "Print all records to stdout (default)"),
        clEnumValN(DumpJSON, "dump-json",
            "Dump all records as "
            "machine-readable JSON"),
        clEnumValN(GenTokens, "gen-tokens",
            "Generate token kinds and keyword "
            "filter")));
\end{cpp}

\item
Main()函数基于action的值执行请求的操作，若在命令行上指定了-{}-gen-tokens，则调用EmitTokensAndKeywordFilter()函数。函数结束后，匿名命名空间关闭:

\begin{cpp}
bool Main(raw_ostream &OS, RecordKeeper &Records) {
    switch (Action) {
    case PrintRecords:
        OS << Records; // No argument, dump all contents
        break;
    case DumpJSON:
        EmitJSON(Records, OS);
        break;
    case GenTokens:
        EmitTokensAndKeywordFilter(Records, OS);
        break;
    }
    return false;
}
} // namespace
\end{cpp}

\item
最后，定义一个main()函数。设置堆栈跟踪处理程序并解析命令行选项之后，将调用TableGenMain()函数来解析TableGen文件并创建记录。若没有错误，该函数也会调用Main()函数:

\begin{cpp}
int main(int argc, char **argv) {
    sys::PrintStackTraceOnErrorSignal(argv[0]);
    PrettyStackTraceProgram X(argc, argv);
    cl::ParseCommandLineOptions(argc, argv);

    llvm_shutdown_obj Y;

    return TableGenMain(argv[0], &Main);
}
\end{cpp}

\end{itemize}

现在实现了TableGen工具。编译后，就可以使用KeywordC运行它。示例输入文件如下:

\begin{shell}
$ tinylang-tblgen --gen-tokens –o TokenFilter.inc KeywordC.td
\end{shell}

生成的C++源代码会写入TokenFilter.inc文件中。

\begin{myTip}{标记过滤器的性能}
对关键字过滤器使用纯二分查找，并不比基于llvm::StringMap类型的实现提供更好的性能。为了超越当前实现的性能，需要生成一个完美的哈希函数。

来自Czech、Havas和Majewski的经典算法可以很容易地实现，并且提供了非常好的性能。它描述在生成最小完美哈希函数的最优算法，信息处理通讯，第43卷，第5期，1992年。参见\url{https:// www.sciencedirect.com/science/article/abs/pii/002001909290220P}。

最先进的算法是Pibiri和Trani的《PTHash: Revisiting FCH Minimal Perfect Hashing, SIGIR ’21》中进行了描述。参见\url{https://arxiv.org/pdf/2104.10402.pdf}。

这两种算法都是生成标记过滤器的不错选择，会比llvm::StringMap更快。
\end{myTip}




















